Databases are used to store information for an innumerable number of applications, including various commercial, industrial, technical, scientific and educational applications. As the reliance on information increases, both the volume of information stored in most databases, as well as the number of users wishing to access that information, likewise increases. Moreover, as the volume of information in a database, and the number of users wishing to access the database, increases, the amount of computing resources required to manage such a database increases as well.
Database management systems (DBMS's), which are the computer programs that are used to access the information stored in databases, therefore often require tremendous resources to handle the heavy workloads placed on such systems. As such, significant resources have been devoted to increasing the performance of database management systems with respect to processing searches, or queries, to databases.
Improvements to both computer hardware and software have improved the capacities of conventional database management systems. For example, in the hardware realm, increases in microprocessor performance, coupled with improved memory management systems, have improved the number of queries that a particular microprocessor can perform in a given unit of time. Furthermore, the use of multiple microprocessors and/or multiple networked computers has further increased the capacities of many database management systems. From a software standpoint, the use of relational databases, which organize information into formally-defined tables consisting of rows and columns, and which are typically accessed using a standardized language such as Structured Query Language (SQL), has substantially improved processing efficiency, as well as substantially simplified the creation, organization, and extension of information within a database.
Furthermore, significant development efforts have been directed toward query “optimization,” whereby the execution of particular searches, or queries, is optimized in an automated manner to minimize the amount of resources required to execute each query. A query optimizer typically generates, for each submitted query, an access plan, which typically incorporates low-level information telling the database engine that ultimately handles a query precisely what steps to take (and in what order) to execute the query. In addition, the access plan may select from different access methods (e.g., table scans or index accesses), based upon the available resources in the system.
In generating an access plan, a query optimizer typically creates multiple potential access plans, and selects the best among those potential access plans based upon the “cost” of each plan. The cost of each plan represents the amount of resources expected to be utilized by the plan (typically expressed in the expected amount of time to execute), and as such, selecting the plan with the lowest cost typically results in the most efficient (and quickest) execution of a query.
The cost of an access plan is typically calculated as a function of both processor cost and the input/output cost. The former is reflective of the expected amount of processor time required to execute the query, while the latter is reflective of the expected amount of time required to retrieve resources needed during query execution, e.g., to retrieve required data from persistent storage such as a disk drive into working memory.
Resources that may need to be retrieved in connection with a query may include, for example, tables or files in a database, as well as hash tables, indices, and the like. Such resources are retrieved into working memory principally for performance reasons, as working memory is usually several orders of magnitude faster than persistent storage media such as disk drives and the like.
In calculating the input/output cost associated with retrieving required resources, however, conventional costing algorithms generally make an assumption that the required resources have not been previously retrieved into working memory. In practice, however, some required resources may have been retrieved into working memory as a result of prior system activity, e.g., the execution of other queries. In such situations, the practical input/output cost associated with retrieving the resources would be significantly less than the cost that would be expected if the resources had to be retrieved from disk in connection with executing the query.
As an example, a query optimizer may receive a query such as:                SELECT * from X, Y        WHERE X.col1=Y.col1 and X.col2=? and Y.col3=?In generating an access plan for such a query, one of the decisions that a query optimizer typically must make is selecting a join order, i.e., whether Y is joined to X or X is joined to Y. It may be the case that if both X and Y and all their indices are not in working memory, then joining Y to X is the optimal join order. However, it may also be the case that, if Y is already in memory, but none of X is in memory (e.g., if a previous query recently performed a table scan of Y), the opposite join order may actually result in better performance, because the practical input/output cost associated with retrieving Y into memory would be negligible. However, given that conventional costing algorithms assume that no required resources have already been retrieved into memory for the purpose of calculating input/output costs, the former join order will always be selected over the latter. Thus, under certain runtime conditions, conventional costing algorithms may make assumptions that are not consistent with actual costs, resulting in the selection of suboptimal access plans under such conditions        
A need therefore exists in the art for an improved manner of calculating the costs of potential access plans, and thus selecting optimal access plans for executing database queries, to address disparities in the actual costs that may arise during runtime.